﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AlgoTest
{
    public class RandomHeap<T> where T : IComparable<T>
    {
        class RandomHeapNode<T> where T : IComparable<T>
        {
            public T Value { get; set; }

            private RandomHeapNode<T> _left;
            private RandomHeapNode<T> _right;
            private static readonly Random Rnd = new Random(DateTime.Now.Millisecond);

            private static void Swap(ref RandomHeapNode<T> first, ref RandomHeapNode<T> second)
            {
                var t = first;
                first = second;
                second = t;
            }

            private void SwapBranches()
            {
                Swap(ref this._left, ref this._right);
            }

            /// <summary>
            /// Merges two randomized heaps and returns the result
            /// </summary>
            /// <param name="first"></param>
            /// <param name="second"></param>
            /// <returns></returns>
            public static RandomHeapNode<T> Merge(RandomHeapNode<T> first, RandomHeapNode<T> second)
            {
                if (first == null)
                    return second;
                if (second == null)
                    return first;

                // If first.Value is more than second.Value, then swapping them.
                // So first now definitely contains the smallest root
                if (first.Value.CompareTo(second.Value) > 0)
                    Swap(ref first, ref second);

                // Now selecting one of children of first to merge it with second
                if ((Rnd.Next() & 1) == 0)
                    first.SwapBranches();

                first._left = Merge(first._left, second);

                return first;
            }


            public void Traverse(IList<T> resultList)
            {
                resultList.Add(this.Value);

                if ((this._left == null) && (this._right == null))
                {
                    return;
                }

                if(this._left == null)
                {
                    this._right.Traverse(resultList);
                }
                else if(this._right == null)
                {
                    this._left.Traverse(resultList);
                }
                else if(this._left.Value.CompareTo(this._right.Value) > 0)
                {
                    this._right.Traverse(resultList);
                    this._left.Traverse(resultList);
                }
                else
                {
                    this._left.Traverse(resultList);
                    this._right.Traverse(resultList);
                }
            }
        }

        private RandomHeapNode<T> _root;

        public void Add(T value)
        {
            if (this._root == null)
            {
                this._root = new RandomHeapNode<T>() {Value = value};
            }
            else
            {
                this._root = RandomHeapNode<T>.Merge
                    (
                        this._root, 
                        new RandomHeapNode<T>(){Value = value}
                    );
            }
        }

        public void Traverse(IList<T> resultList)
        {
            if(this._root != null)
            {
                this._root.Traverse(resultList);
            }
        }
    }
}
